/*
 * scheduler_o_1.cpp
 *
 *  Created on: 2011-5-26
 *      Author: chenl
 */
#include "scheduler_o_1.h"
#include "logengine/buffedlog.h"
#include "common/common_util.h"
#include "datetime/datetime.h"

#define ON_RUNQUEUE_WEIGHT	 30
#define CHILD_PENALTY		 95
#define PARENT_PENALTY		100
#define EXIT_WEIGHT		  	3
#define PRIO_BONUS_RATIO	 25
#define MAX_BONUS		(MAX_USER_PRIO * PRIO_BONUS_RATIO / 100)
#define INTERACTIVE_DELTA	  2
#define MAX_SLEEP_AVG		(DEF_TIMESLICE * MAX_BONUS)
#define STARVATION_LIMIT	(MAX_SLEEP_AVG)
#define NS_MAX_SLEEP_AVG	(JIFFIES_TO_NS(MAX_SLEEP_AVG))

#define CURRENT_BONUS(p) \
	(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
		MAX_SLEEP_AVG)

#define GRANULARITY	(10 * HZ / 1000 ? : 1)

#define TIMESLICE_GRANULARITY(p)	(GRANULARITY * \
		(1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)))

#define SCALE(v1,v1_max,v2_max) \
	(v1) * (v2_max) / (v1_max)

#define DELTA(p) \
	(SCALE(TASK_NICE(p), 40, MAX_BONUS) + INTERACTIVE_DELTA)

#define TASK_INTERACTIVE(p) \
	((p)->prio <= (p)->static_prio - DELTA(p))

#define INTERACTIVE_SLEEP(p) \
	(JIFFIES_TO_NS(MAX_SLEEP_AVG * \
		(MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))

#define TASK_PREEMPTS_CURR(p, rq) \
	((p)->prio < (rq)->curr->prio

#define NS_TO_JIFFIES(TIME)	((TIME) / (1000000000 * GET_PARAMCONFIG_INSTANCE().GetSlowerTimes() / HZ))
#define JIFFIES_TO_NS(TIME)	((TIME) * (1000000000 * GET_PARAMCONFIG_INSTANCE().GetSlowerTimes() / HZ))

#define jiffies (NS_TO_JIFFIES(CDateTime::CurrentDateTime().uSeconds()))

#define EXPIRED_STARVING(rq) \
			((STARVATION_LIMIT && ((rq)->expired_timestamp && \
					(jiffies - (rq)->expired_timestamp >= \
							STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
							(GET_PROCESSMGT_INSTANCE().CurrentTask()->task.static_prio > (rq)->best_expired_prio))

CScheduler_O_1::CScheduler_O_1() :
	logEngine(GET_PSTHREADLOG_INSTANCE())
{

}

CScheduler_O_1::~CScheduler_O_1()
{

}

void CScheduler_O_1::schedule()
{
	CProcessMgt& processMgt = GET_PROCESSMGT_INSTANCE();
	CTask* pCurrentTask = processMgt.CurrentTask();
	if (unlikely(NULL == pCurrentTask))
	{
		logEngine.WriteLog(enmLogLevel_FATAL,
				"pCurrentTask is NULL in CScheduler_O_1::schedule()!");
		return;
	}

	unsigned long *switch_count;
	int64_t now;
	int64_t run_time;

	CPrioRunQueue::RunQueue* pArray = NULL;
	CTask* pPrevTask = NULL;
	CTask* pNextTask = NULL;

	CPrioRunQueue* rq = static_cast<CPrioRunQueue*> (processMgt.pRunQueue);
	assert(NULL != rq);

need_resched:
	logEngine.WriteLog(enmLogLevel_INFO,
			"Start scheduling(current=%d, current->counter=%d)!",
			pCurrentTask->task.pid, pCurrentTask->task.counter);
	pPrevTask = pCurrentTask;
	now = CDateTime::CurrentDateTime().uSeconds();
	logEngine.WriteLog(
			enmLogLevel_INFO,
			"(now - pPrevTask->task.timestamp(%llu)) =%llu, NS_MAX_SLEEP_AVG=%llu",
			pPrevTask->task.timestamp, (now - pPrevTask->task.timestamp),
			NS_MAX_SLEEP_AVG);
	if ((now - pPrevTask->task.timestamp) < (unsigned long long)NS_MAX_SLEEP_AVG)
	{
		run_time = now - pPrevTask->task.timestamp;
		if (unlikely((now - pPrevTask->task.timestamp) < 0))
			run_time = 0;
	}
	else
		run_time = NS_MAX_SLEEP_AVG;

	/*
	 * Tasks charged proportionately less run_time at high sleep_avg to
	 * delay them losing their interactive status
	 */
	run_time /= (CURRENT_BONUS(&pPrevTask->task) ? : 1);


	if (unlikely(pPrevTask->task.flags & PF_DEAD))
		pPrevTask->task.state = EXIT_DEAD;

	switch_count = &pPrevTask->task.nivcsw;
	if (pPrevTask->task.state)
	{
		logEngine.WriteLog(enmLogLevel_INFO,
				"prev(pid=%d)->state is not runnable", pPrevTask->task.pid);
		switch_count = &pPrevTask->task.nvcsw;
		if (unlikely((pPrevTask->task.state & TASK_INTERRUPTIBLE) &&
				unlikely(pPrevTask->SignalPending())))
			pPrevTask->task.state = TASK_RUNNING;
		else
		{
			if (pPrevTask->task.state == TASK_UNINTERRUPTIBLE)
				++rq->nr_uninterruptible;
			deactivate_task(*pPrevTask, *rq);
		}
	}

	logEngine.WriteLog(
			enmLogLevel_INFO,
			"current(pid=%d) rq(nr_running=%u,nr_switching=%u,nr_uninterruptible=%u,expired_timestamp=%u,timestamp_last_tick=%llu,nr_switches=%u,best_expired_prio=%d)",
			pCurrentTask->task.pid, rq->nr_running, rq->nr_switching, rq->nr_uninterruptible,
			rq->expired_timestamp, rq->timestamp_last_tick, rq->nr_switches,
			rq->best_expired_prio);

	if (unlikely(!(rq->nr_running)))
	{
		pNextTask = processMgt.InitTask();
		rq->expired_timestamp = 0;
		logEngine.WriteLog(
				enmLogLevel_INFO,
				"No running tasks in runqueue! pNextTask=initTask(%d), goto switch_tasks",
				pNextTask->task.pid);
		if (!rq->nr_running)
			goto switch_tasks;
	}

	pArray = rq->pActiveQueue;
	logEngine.WriteLog(
			enmLogLevel_INFO,
			"Pick up active array(array=0x%08x,nr_active=%d,bitmap=[%08x %08x %08x %08x %08x])", pArray,
			pArray->nr_active, pArray->bitmap[0], pArray->bitmap[1],
			pArray->bitmap[2], pArray->bitmap[3], pArray->bitmap[4]);
	if (unlikely(!pArray->nr_active))
	{
		rq->SwitchArray();
		pArray = rq->pActiveQueue;
		rq->expired_timestamp = 0;
		rq->best_expired_prio = MAX_PRIO;
		logEngine.WriteLog(enmLogLevel_INFO,
				"No running tasks in active array! Switch arrays! current(pid=%d) active=0x%08x", pCurrentTask->task.pid, rq->pActiveQueue);
	}
	pNextTask = processMgt.FirstTaskFromRunQueue();
	assert(NULL != pNextTask);
	logEngine.WriteLog(enmLogLevel_INFO, "Pick up task(pid=%d,time_slice=%d,prio=%d,static_prio=%d) as pNextTask",
			pNextTask->task.pid, pNextTask->task.time_slice, pNextTask->task.prio, pNextTask->task.static_prio);

	if (!rt_task(&pNextTask->task) && pNextTask->task.activated > 0)
	{
		logEngine.WriteLog(enmLogLevel_INFO,
				"pNextTask(pid=%d) is NOT realtime task and is activated(%d)",
				pNextTask->task.pid, pNextTask->task.activated);
		unsigned long long delta = now - pNextTask->task.timestamp;
		if (unlikely((long long)(now - pNextTask->task.timestamp) < 0))
			delta = 0;

		if (1 == pNextTask->task.activated)
			delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

		pArray = pNextTask->task.array;
		assert(NULL != pArray);
		dequeue_task(*pNextTask, *pArray);
		recalc_task_prio(&pNextTask->task, pNextTask->task.timestamp + delta);
		enqueue_task(*pNextTask, *pArray);
		logEngine.WriteLog(enmLogLevel_INFO,
				"recalc task(pid=%d) prio, new task prio=%d,timestamp=%d,delta=%d",
				pNextTask->task.prio, pNextTask->task.timestamp, delta);
	}
	pNextTask->task.activated = 0;
	logEngine.WriteLog(enmLogLevel_INFO,
			"pNextTask(pid=%d) activated is reset to 0");

switch_tasks:
	update_cpu_clock(&pPrevTask->task, rq, now);

	pPrevTask->task.sleep_avg -= run_time;
	logEngine.WriteLog(enmLogLevel_INFO, "Set pPrevTask(pid=%d) sleep_avg(%lu)-=runtime(%llu)"
			, pPrevTask->task.pid, pPrevTask->task.sleep_avg, run_time);
	if ((long) pPrevTask->task.sleep_avg <= 0)
		pPrevTask->task.sleep_avg = 0;
	pPrevTask->task.timestamp = pPrevTask->task.last_ran = now;

	if (likely(pPrevTask != pNextTask))
	{
		pNextTask->task.timestamp = now;
		++rq->nr_switches;
		//		rq->curr = next;
		++*switch_count;

		processMgt.SetCurrentTask(*pNextTask);
		pCurrentTask = processMgt.CurrentTask();
		logEngine.WriteLog(enmLogLevel_INFO,
				"Finish switching! current(pid=%d), prev(pid=%d), next(pid=%d)",
				pCurrentTask->task.pid, pPrevTask->task.pid,
				pNextTask->task.pid);
	}
	else
		logEngine.WriteLog(
				enmLogLevel_INFO,
				"Finish switching but pPrevTask==pNextTask! current(pid=%d), prev(pid=%d), next(pid=%d)",
				pCurrentTask->task.pid, pPrevTask->task.pid,
				pNextTask->task.pid);

	pPrevTask = pCurrentTask;

	if (pCurrentTask->task.need_resched)
	{
		pCurrentTask->task.need_resched = 0;
		goto need_resched;
	}
}

void CScheduler_O_1::recalc_task_prio(struct task_struct *p,
		unsigned long long now)
{
	/* Caller must always ensure 'now >= p->timestamp' */
	assert(now >= p->timestamp);
	unsigned long long __sleep_time = now - p->timestamp;
	unsigned long sleep_time;

	logEngine.WriteLog(enmLogLevel_INFO, "Start CScheduler_O_1::recalc_task_prio()!task(pid=%d)", p->pid);

	if (__sleep_time > (unsigned long long)NS_MAX_SLEEP_AVG)
		sleep_time = NS_MAX_SLEEP_AVG;
	else
		sleep_time = (unsigned long) __sleep_time;

	if (likely(sleep_time > 0))
	{
		/*
		 * User tasks that sleep a long time are categorised as
		 * idle and will get just interactive status to stay active &
		 * prevent them suddenly becoming cpu hogs and starving
		 * other processes.
		 */
		logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d)'s sleep_time(%lu)>0", p->pid, sleep_time);
		if (p->activated != -1 && sleep_time > (unsigned long long)INTERACTIVE_SLEEP(p))
		{
			logEngine.WriteLog(enmLogLevel_INFO,
					"task(pid=%d)'s activated(%d)!=-1 && sleep_time(%lu) > INTERACTIVE_SLEEP(%lu), the task slept long time and categorised as idle!",
					p->pid, p->activated, p->sleep_time, INTERACTIVE_SLEEP(p));
			p->sleep_avg = JIFFIES_TO_NS(MAX_SLEEP_AVG -
					DEF_TIMESLICE);
			logEngine.WriteLog(enmLogLevel_INFO, "Set task(pid=%d)'s sleep_avg(%lu)", p->pid, p->sleep_avg);
		}
		else
		{
			/*
			 * The lower the sleep avg a task has the more
			 * rapidly it will rise with sleep time.
			 */
			logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d) has low sleep_time(%lu) or is is waking from uninterruptible sleep(if activated(=%d)==-1)",
					p->pid, p->sleep_time, p->activated);

			sleep_time *= (MAX_BONUS - CURRENT_BONUS(p)) ? : 1;

			/*
			 * Tasks waking from uninterruptible sleep are
			 * limited in their sleep_avg rise as they
			 * are likely to be waiting on I/O
			 */
			if (p->activated == -1)
			{
				if (p->sleep_avg >= (unsigned long long)INTERACTIVE_SLEEP(p))
					sleep_time = 0;
				else if (p->sleep_avg + sleep_time >= (unsigned long long)INTERACTIVE_SLEEP(p))
				{
					p->sleep_avg = INTERACTIVE_SLEEP(p);
					sleep_time = 0;
				}
			}

			/*
			 * This code gives a bonus to interactive tasks.
			 *
			 * The boost works by updating the 'average sleep time'
			 * value here, based on ->timestamp. The more time a
			 * task spends sleeping, the higher the average gets -
			 * and the higher the priority boost gets as well.
			 */
			p->sleep_avg += sleep_time;

			if (p->sleep_avg > (unsigned long long)NS_MAX_SLEEP_AVG)
				p->sleep_avg = NS_MAX_SLEEP_AVG;
			logEngine.WriteLog(enmLogLevel_INFO, "Set task(pid=%d) sleep_avg(%lu)+=sleep_time(%lu)",
					p->pid, p->sleep_avg, sleep_time);
		}
	}
	p->prio = effective_prio(p);
}

void CScheduler_O_1::scheduler_tick()
{
	CProcessMgt& processMgt = GET_PROCESSMGT_INSTANCE();
	CTask* pTask = processMgt.CurrentTask();
	if (NULL == pTask)
	{
		logEngine.WriteLog(enmLogLevel_ERROR,
				"Get current task failed when CScheduler_O_1::scheduler_tick()!");
		return;
	}

	int64_t now = CDateTime::CurrentDateTime().uSeconds();
	CPrioRunQueue* rq = static_cast<CPrioRunQueue*> (processMgt.pRunQueue);
	struct task_struct* p = &pTask->task;
	struct task_struct* idle = &CTask::InitTask().task;

	logEngine.WriteLog(enmLogLevel_INFO,
					"start CScheduler_O_1::scheduler_tick() current(pid=%d),time_slice=%d,prio=%d,static_prio=%d",
					p->pid, p->time_slice, p->prio, p->static_prio);

	update_cpu_clock(p, rq, now);

	rq->timestamp_last_tick = now;

	if (idle == p)
	{
		return;
	}

	if (p->array != rq->pActiveQueue)
	{
		logEngine.WriteLog(enmLogLevel_INFO, "p(pid=%d)->array(0x%08x) != rq->pActiveQueue(0x%08x), Set need_resched!",
				p->pid, p->array, rq->pActiveQueue);
		p->need_resched = 1;
		return;
	}

	if (rt_task(p))
	{
		/*
		 * RR tasks need a special form of timeslice management.
		 * FIFO tasks have no timeslices.
		 */
		logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d) is realtime task");

		if ((p->policy == SCHED_RR) && !p->time_slice--)
		{
			p->time_slice = task_timeslice(p);
			p->first_time_slice = 0;
			p->need_resched = 1;

			/* put it at the end of the queue: */
			int32_t ret = rq->pActiveQueue->queue[p->prio / 32].MoveTaskToTail(*pTask);
			assert (0 <= ret);
		}
		return;
	}
	if (!p->time_slice--)
	{
		logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d)'s time_slice is exhausted!", p->pid);
		dequeue_task(*pTask, *rq->pActiveQueue);
		p->need_resched = 1;
		p->prio = effective_prio(p);
		p->time_slice = task_timeslice(p);
		p->first_time_slice = 0;
		logEngine.WriteLog(enmLogLevel_INFO, "recalc task(pid=%d) prio(%d), time_slice(%d)",
				p->pid, p->prio, p->time_slice);

		if (!rq->expired_timestamp)
			rq->expired_timestamp = NS_TO_JIFFIES(now);
		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq))
		{
#ifdef DEBUG
			if (!TASK_INTERACTIVE(p))
				logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d) is NOT interactive!", p->pid);
			if (EXPIRED_STARVING(rq))
				logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d) is starving!", p->pid);
#endif
			enqueue_task(*pTask, *rq->pExpireQueue);
			if (p->static_prio < rq->best_expired_prio)
				rq->best_expired_prio = p->static_prio;
		}
		else
		{
			enqueue_task(*pTask, *rq->pActiveQueue);
		}
	}
	else
	{
		/*
		 * Prevent a too long timeslice allowing a task to monopolize
		 * the CPU. We do this by splitting up the timeslice into
		 * smaller pieces.
		 *
		 * Note: this does not mean the task's timeslices expire or
		 * get lost in any way, they just might be preempted by
		 * another task of equal priority. (one with higher
		 * priority would have preempted this task already.) We
		 * requeue this task to the end of the list on this priority
		 * level, which is in essence a round-robin of tasks with
		 * equal priority.
		 *
		 * This only applies to tasks in the interactive
		 * delta range with at least TIMESLICE_GRANULARITY to requeue.
		 */

#ifdef DEBUG
			if (TASK_INTERACTIVE(p))
				logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d) still has unused time_slice(%d) and is interactive!", p->pid, p->time_slice);
			if (!((task_timeslice(p) - p->time_slice)
					% TIMESLICE_GRANULARITY(p)))
				logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d) still has unused time_slice(%d) and !((task_timeslice(%d) - p->time_slice(%d)) % TIMESLICE_GRANULARITY(%d))", p->pid, p->time_slice, task_timeslice(p), p->time_slice, TIMESLICE_GRANULARITY(p));
			if (p->array == rq->pActiveQueue)
				logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d) still has unused time_slice(%d) and p->array(0x%08x) == rq->pActiveQueue(0x%08x)", p->pid, p->time_slice, p->array, rq->pActiveQueue);
#endif
		if (TASK_INTERACTIVE(p) && !((task_timeslice(p) - p->time_slice)
				% TIMESLICE_GRANULARITY(p)) && (p->time_slice
				>= (unsigned)TIMESLICE_GRANULARITY(p)) && (p->array == rq->pActiveQueue))
		{
			logEngine.WriteLog(enmLogLevel_INFO, " Prevent a too long timeslice allowing a task to monopolize the CPU. requeue task(pid=%d) and set need_resched", p->pid);
			rq->pActiveQueue->queue[p->prio / 32].MoveTaskToTail(*pTask);
			p->need_resched = 1;
		}
	}

}

int CScheduler_O_1::effective_prio(struct task_struct *p)
{
	int bonus, prio;

	if (rt_task(p))
	{
		logEngine.WriteLog(enmLogLevel_INFO, "task(pid=%d) is realtime, effective_prio=%d", p->pid, p->prio);
		return p->prio;
	}

	bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;

	prio = p->static_prio - bonus;
	if (prio < MAX_RT_PRIO)
		prio = MAX_RT_PRIO;
	if (prio > MAX_PRIO - 1)
		prio = MAX_PRIO - 1;
	logEngine.WriteLog(enmLogLevel_INFO, "calc task(pid=%d) effective_prio! prio(%d)=static_prio(%d)-CURRENT_BONUS(%d)-MAX_BONUS(%d)/2",
			p->pid, p->prio, p->static_prio, CURRENT_BONUS(p), MAX_BONUS);
	return prio;
}

